/**
 * 4. Median of Two Sorted Arrays
 * https://leetcode.com/problems/median-of-two-sorted-arrays/
 */
class MedianOfTwoSortedArrays {

    /**
     *  方法：二分查找。在较短数组上二分查找，找到一个位置i，使得a[i]<=b[j+1] && b[j]<=a[i+1]，其中j=(m+n+1)/2-i。
     *  这样可以保证左半部分的数都小于等于右半部分的数。中位数就可以由左半部分的最大值和右半部分的最小值得到
     *  Args:
     *      a: 第一个有序数组
     *      b: 第二个有序数
     *  Returns:
     *      两个有序数组的中位
     *  Time: O(log(min(m,n))) - m和n分别是两个数组的长度，在较短数组上二分查
     *  Space: O(1) - 只使用常数额外空间
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        //分割线左侧元素个数需要满足 m + (n - m + 1) / 2
        int totalLeft = (m + n + 1) / 2;
        // 在nums1区间 [0,m] 里查找分割线
        // 使得 nums1[i - 1] <= nums2[j] && nums[j - 1] < = nums1[i]
        int left = 0;
        int right = m;
        while (left < right){
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]){
                // [left, i-1]
                right = i - 1;
            }else{
                //[i, right]
                left = i;
            }
        }
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i-1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j-1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        int maxLeft = Math.max(nums1LeftMax, nums2LeftMax);
        if((m + n) % 2 == 1){
            return maxLeft;
        } else {
            int minRight = Math.min(nums1RightMin, nums2RightMin);
            return (double)(maxLeft + minRight) / 2;
        }
    }
    
    public static void main(String[] args) {
        MedianOfTwoSortedArrays medianFinder = new MedianOfTwoSortedArrays();
        // 测试用例
        testMedian(medianFinder, new int[]{1, 3}, new int[]{2}, 2.0);
        testMedian(medianFinder, new int[]{1, 2}, new int[]{3, 4}, 2.5);
        // ... 可以添加更多测试用例 ...
    }

    private static void testMedian(MedianOfTwoSortedArrays medianFinder, int[] nums1, int[] nums2, double expected) {
        double result = medianFinder.findMedianSortedArrays(nums1, nums2);
        System.out.println("实际输出: " + result + ", 预期输出: " + expected);
    }
}